package com.sise.Tree;

/**
 *      101. 对称二叉树
 *      给定一个二叉树，检查它是否是镜像对称的。
 *
 *      例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 *
 *              1
 *             / \
 *            2   2
 *           / \ / \
 *          3  4 4  3
 *
 *      递归：
 *      1、终止条件：如果为 空，那么说明为 ture
 *      2、递归返回：返回 这两棵树的子树 是否对称 boolean
 *      3、递归动作：比较当前的左右子树值是否相同，递归左右子树。 (递归) 左节点的左孩子 和 右节点的右孩子 && 左节点的右孩子 和 右节点的左孩子
 */
public class _101_isSymmetric {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        // 因为涉及到 左右子树需要同时作用，故此调用了其他的递归函数(两个子树，参数)，而不是在自己本身调用。
        return dfs(root.left, root.right);
    }

    public boolean dfs(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;     // 如果左右子节点为空，那么就进行截停操作，不用对 第三层进行对比
        if (left == null || right == null) return false;
        return left.val == right.val                        // 比较当前节点的左右子节点的值
                && dfs(left.left, right.right)              // 递归 左节点的左孩子 和 右节点的右孩子
                && dfs(left.right, right.left);             // 注意：这里不是比较，而是递归操作。 比较 留给 递归体来判断即可
    }
}
